//todo: check how ArrayList implement the template
public class THeap<Type extends HeapItem> {
private transient HeapItem [] dataArray;
private int nextIndex;

public THeap(int size){
	dataArray = new HeapItem[size];
	nextIndex = 0;
	}


public int Size(){
	return nextIndex;
}



public int GetSmallerChildIndex(int index){
	int leftChildIndex = index * 2 + 1;
	int rightChildIndex = index * 2 + 2;
	if(leftChildIndex < nextIndex)
	{
		if(rightChildIndex < nextIndex)
		{
			if(dataArray[index].isLargerThan(dataArray[leftChildIndex]) 
					&& dataArray[rightChildIndex].isLargerThan(dataArray[leftChildIndex]))
			{
				return leftChildIndex;
			}
			else if(dataArray[index].isLargerThan(dataArray[rightChildIndex]) 
					&& dataArray[leftChildIndex].isLargerThan(dataArray[rightChildIndex]))
			{
				return rightChildIndex;
			}
		}
		else if(dataArray[index].isLargerThan(dataArray[leftChildIndex]))
		{
			return leftChildIndex;
		}
	}
	
	return -1;
}

@SuppressWarnings("unchecked")
public Type ExtractMin(){
	HeapItem minObj = dataArray[0];
	
	dataArray[0] = dataArray[--nextIndex];
	
	int index = 0;
	while(index < nextIndex){
		int swapIndex = GetSmallerChildIndex(index);
		
		if(swapIndex == -1)
			break;
		
		HeapItem temp = dataArray[index];
		dataArray[index] = dataArray[swapIndex];
		dataArray[index].setHeapIndex(index);
		dataArray[swapIndex] = temp;
		dataArray[swapIndex].setHeapIndex(swapIndex);
		index = swapIndex;
	}
	return (Type)minObj;
}


public int Insert(HeapItem item){
	if(nextIndex >= dataArray.length)
		return -1;
	
	int index = nextIndex;
	dataArray[index] = item;
	dataArray[index].setHeapIndex(index);
	nextIndex++;
	
	return UpdatePosition(index);	
}


public int UpdatePosition(int index){
	int parentIndex = (index - 1)/2;
	
	while(parentIndex >= 0 && dataArray[index].isLessThan(dataArray[parentIndex]))
	{
		HeapItem temp = dataArray[index];
		dataArray[index] = dataArray[parentIndex];
		dataArray[index].setHeapIndex(index);
		dataArray[parentIndex] = temp;
		dataArray[parentIndex].setHeapIndex(parentIndex);
		index = parentIndex;
		parentIndex = (index - 1) / 2;
	}
	
	return index;
}


public void PrintData(){
	for(int i = 0; i < this.Size(); i++)
	{
		System.out.print(i + " :");
		dataArray[i].PrintData();
		System.out.print("\n");
	}
}
}
